Over the last decades there has been significant progress within the field of autonomous vehicles. From first presented as a futuristic idea in the Futurama exhibit at the 1939 New York World's Fair, ventures such as The DARPA Grand and Urban challenge, Safe Road Trains for the Environment (SARTRE), and the Google autonomous car have demonstrated the possibility and feasibility of the technology. Nonetheless, there is still a large gap between the demonstrated technology and commercially available vehicle systems.
Current Advanced Driver Assistance Systems (ADAS), such as Adaptive Cruise Control (ACC), Lane Keeping Aid (LKA), Traffic Jam Assist (TJA), and collision warning with auto brake, have been shown to improve the driver's comfort and safety. It is therefore expected that further developed autonomous functionality will continue to contribute to enhance driver convenience, traffic efficiency, and overall traffic safety.
Several approaches to trajectory planning for yielding maneuvers have previously been proposed where the most common include but are not limited to, cell decomposition methods e.g. A*,D*, and Rapidly exploring Random Trees (RRTs), cost- and utility based evaluation functions or constraints, and optimal control.
In cell decomposition methods the state space is divided into cells which can be assigned obstacle and goal dependent costs, thus allowing trajectory planning algorithms e.g. A*, and D* or randomized sampling based algorithms e.g. RRTs to search for the optimal collision free trajectory by exploring the cell space. By their nature, cell decomposition methods can be utilized for trajectory planning for various traffic situations and maneuvers. However, the algorithms can require significant computer resources since the number of cells grows exponentially with the dimension of the state space. Moreover, the optimality of the planned trajectory is only guaranteed up to cell resolution.
Cost- and utility-based functions or constraints are commonly used due to their straightforwardness and simplicity when applied to a certain traffic situation e.g. highway driving. By e.g. adding a cost term or constraint regarding obstacle proximity, collision free trajectories can be determined. However, these types of cost functions and constraints are normally non-linear and/or non-, thus providing no guarantee of generating an optimal solution. Further, utility- and cost based approaches do not normally include a search through the configuration space but rather use the cost functions or constraints as a mean of determining which maneuver to perform within a limited set of predefined trajectories.
In terms of an optimal control framework, trajectory planning is formulated as the solution of a constrained optimal control problem over a finite time horizon. In particular, a cost function is optimized subject to a set of constraints which generally includes the vehicle dynamics, design and physical constraints, and additional constraints introduced to avoid collision with surrounding vehicles. The main advantage of resorting to the optimal control formulation is that collision avoidance is guaranteed, provided that the optimization problem is feasible.
However, vehicle dynamics and collision avoidance constraints generally result in non-linear and/or mixed integer inequalities, which may lead to prohibitive computational complexity that prevents the real-time execution of the trajectory planning algorithm. To reduce the computational burden a particular optimal control trajectory planning algorithm is therefore generally tailored to a certain traffic situation or maneuver.
Although the above mentioned methods for autonomous trajectory planning do give good results in a number of applications, they also come with various drawbacks where the main limitation involves the trade-off between required computational resources, solution optimality and verification, and ability to generate smooth collision-free trajectories which are applicable to general traffic situations.